package algocasts;

public class P84_numberIfCoinCombination {
    public int coinCombination(int[] coins, int start, int sum) {
        if (sum == 0) return 1;
        if (sum < 0) return 0;
        int res = 0;
        for (int i = start; i < coins.length; i++) {
            res += coinCombination(coins, i, sum - coins[i]);
        }
        return res;
    }

    public int change_Recursive(int sum, int[] coins) {
        return coinCombination(coins, 0, sum);
    }

    // Time: O(n*sum)  Space: O(n*sum)
    public int change_DP(int sum, int[] coins) {
        int[][] d = new int[coins.length + 1][sum + 1];
        for (int i = 0; i <= coins.length; ++i) d[i][0] = 1;
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= sum; j++) {
                int useCurCoin = j >= coins[i - 1] ? d[i][j - coins[i - 1]] : 0;
                d[i][j] = d[i - 1][j] + useCurCoin;
            }
        }
        return d[coins.length][sum];
    }

    // Time: O(n*sum)  Space: O(sum)
    public int change_DPOSum(int sum, int[] coins) {
        int[] d = new int[sum + 1];
        d[0] = 1;
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= sum; j++) {
                int useCurCoin = j >= coins[i - 1] ? d[j - coins[i - 1]] : 0;
                d[j] = d[j] + useCurCoin;
            }
        }
        return d[sum];
    }
}
